A modular multiplication operation consists of carrying out the following operation:a·b mod n;where a, b and n are integers, n being called the modulus.
In a conventional manner, in order to effect a modular multiplication the computing means first of all carry out a multiplication of a by b, followed by modulo n reduction. The time for performing this operation is proportional to k2 where k is the number of bits necessary in order to encode respectively a, b and n in binary form.
In a manner which is equally well known to mathematicians, a modular multiplication can be carried out by the Montgomery method. This method introduces Montgomery products as described in the document by Cetin Kaya Koç, “High Speed RSA Implementation”, which may be obtained from the following address:                RSA Laboratories        RSA Data Security, Inc.        100, Marine Parkway, Suite 500        Redwood City, Calif. 94-65-1031        U.S.A.        
In the following description this document will be referred to as D1. The subject matter of the document “High Speed RSA Implementation is hereby incorporated by reference in its entirety.
A modular exponentiation operation consists of carrying out the following operation:xc mod n;where x, c and n are integers, n being the modulus.
The calculation of this exponentiation by known methods, such as for example the “square and multiply” method, involves k modular multiplications, k being the number of bits necessary in order to encode respectively x, c and n in binary form. Thus it is assumed that the time for performing this operation is proportional to k3.
The modular exponentiation operations constitute basic operations of data encrypting/decrypting devices. For example, the encrypting/decrypting devices implementing the RSA (Rivest-Shamir-Adleman) use modular exponentiations.
These devices currently exist in various such as electronic components or electronic cards intended to be associated with computing means in order to perform and/or to speed up the encrypting/decrypting operations.
Electronic commerce, particularly on the Internet, uses a large number of these encrypting/decrypting devices in order to encrypt and decrypt commercial operations such as payments. The turnover of companies carrying out electronic commerce is therefore limited by the number of encrypting and decrypting operations which can be performed per second.
Consequently it will be imagined that it is important to speed up the time required for performing a Montgomery product calculation, a multiplication and a modular exponentiation on a machine equipped with computing means.
Therefore the object of the invention is to propose a method and a device for speeding up the time required to perform a Montgomery product calculation, a modular multiplication and a modular exponentiation on a machine equipped with computing means.
The invention therefore relates to a method for speeding up the time required to perform a Montgomery product calculation by applying the high-radix Montgomery method on computing hardware, the said method comprising a loop of operations consisting of reiterating successive operations, wherein in particular:                a first addition operation between a value of one of several first products, denoted āi· b and a value of a variable, denoted u, according to a first relationship u:=u+āi· b;        a second addition operation between a value of one of several second products, denoted m·n, and a value of the variable u according to a second relationship u:=u+m·n;characterised in that at least the said first and second addition operations are carry-save addition operations in order to speed up the time required for performing an addition.        
According to other characteristics and advantages of the invention, the method comprises:                in a loop of operations a third operation of division of the variable u by a power of 2, denoted 2ω, where ω is the radix, according to a third relationship        
      u    :=          u              2        ω              ,characterised in that the variable u is registered in the form of a carry-save ordered pair formed by two variables, denoted C and S, for performing operations of the loop, and that the third operation of division of the variable u in the form of a carry-save ordered pair is carried out in two steps, namely:                a preliminary step of calculation and storage of a carry digit, denoted Re, which is at risk of being lost by the division of each variable C and S by the power of 2;        a step of division of each variable C and S by the power of 2;        the preliminary step of calculation of the carry digit Re comprises the operation of adding in a conventional manner ω least significant bits of the variable C, denoted C0, to ω least significant bits of the variable S, denoted S0, according to a fourth relationship Re:=C0+S0;        a recombination of u on the basis of the variables C and S of the carry-save ordered pair and of the carry digit Re comprises the operation of shifting to the right by ω bits the carry digit Re and in a conventional manner adding the result obtained to the variables C and S according to a fifth relationship u:=C+S+Re/2ω;        it comprises at the end of performing the loop of operations:        a step of recombination (84) of the variable u on the basis of at least the values of the variables C and S of the carry-save ordered pair calculated during the performance of the loop of operations, and        a step of reduction (86) of the variable u according to a sixth relationship u:=u−n, where n is a modulus,        the said steps of recombination and of reduction of the variable u overlapping in such a way as to speed up the time required to perform them;        the radix ω is equal to 4 bits in order to optimise the time required for performing the calculation of a Montgomery product on the input variables of the Montgomery product encoded on 512 or 1024 bits;        the first products āi· b are pre-calculated before performing the loop of operations; and        the second products m·n are pre-calculated before performing the loop of operations.        
The invention also relates to a method of speeding up the time required to perform the calculation of a first and a second Montgomery product by applying for each product a method including at least one first step during which the first addition operation for the first product is carried out at the same time as the second addition operation for the second product.
According to other characteristics and advantages of this method for speeding up the time required to perform the calculation of a first and a second Montgomery product:                it comprises at least a second step shifted in time with respect to the first, during which the second addition operation for the first product is carried out at the same time as the first addition operation for the second product;        it comprises at the end of performing the loop of operations:        a step of recombination then of reduction for the first product performed first; and then,        a step of recombination then of reduction for the second product performed second;        one of the input variables of the first Montgomery product performed first is made up of the least significant bits of a variable, and one of the input variables of the second Montgomery product performed second is made up of the most significant bits of this same variable.        
The invention also relates to a method of speeding up the time required for performing a modular multiplication calculation by applying a method implementing Montgomery products, characterised in that the calculation of the Montgomery products is carried out by applying at least one of the methods according to the invention.
According to other characteristics and advantages of this method for speeding up the time required for performing a modular multiplication calculation:                the said method implementing Montgomery products is the Montgomery method.        